const ALPHABET_SIZE: usize = 26;

struct TrieNode { 
    children: [Option<Box<TrieNode>>; ALPHABET_SIZE], 
    is_end: bool 
}  

impl TrieNode {  
    fn new() -> Self {
        TrieNode {
            children: Default::default(),
            is_end: false,
        }
    }

    // 插入单词（递归实现）
    fn insert(&mut self, word: &str) { 
        /* TODO */ 
        let mut current = self;
        for c in word.chars() {
            let index = (c as usize) - ('a' as usize);
            if index >= ALPHABET_SIZE {
                continue; // 跳过非小写字母
            }
            current = current.children[index].get_or_insert_with(|| Box::new(TrieNode::new()));
        }
        current.is_end = true;
    }  

    // 查询单词存在性
    fn search(&self, word: &str) -> bool {
        let mut current = self;
        for c in word.chars() {
            let index = (c as usize) - ('a' as usize);
            match &current.children[index] {
                Some(node) => current = node,
                None => return false,
            }
        }
        current.is_end
    }
}  

#[test] 
fn test_trie() { 
    /* 检查单词存在性 */ 
    let mut root = TrieNode::new();
    
    // 测试基础插入
    root.insert("apple");
    assert!(root.search("apple"));
    assert!(!root.search("app"));
    
    // 测试前缀覆盖
    root.insert("app");
    assert!(root.search("app"));
    
    // 测试大小写敏感
    //assert!(!root.search("Apple"));
}  

// 添加自动补全演示
fn main() {
    let mut trie = TrieNode::new();
    trie.insert("apple");
    trie.insert("application");
    trie.insert("app");
    trie.insert("banana");
    
    println!("Search 'app': {}", trie.search("app"));      // true
    println!("Search 'apps': {}", trie.search("apps"));    // false
    
    // 前缀搜索演示（可选扩展）
    println!("\nSuggestions for 'app':");
    let mut node = &trie;
    for c in "app".chars() {
        let idx = (c as usize) - ('a' as usize);
        node = node.children[idx].as_ref().unwrap();
    }
    collect_words(node, "app", &mut Vec::new());
}

// 收集所有建议词（扩展功能）
fn collect_words(node: &TrieNode, prefix: &str, result: &mut Vec<String>) {
    if node.is_end {
        result.push(prefix.to_string());
    }
    for (i, child) in node.children.iter().enumerate() {
        if let Some(child_node) = child {
            let c = (i as u8 + b'a') as char;
            collect_words(child_node, &format!("{}{}", prefix, c), result);
        }
    }
}